package array

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
// 检查是否是合法的数独
// 算法: 遍历
// 时间复杂度: O(n)
func isValidSudoku(board [][]byte) bool {
	sdLen := 9
	// 检查每一列
	for x := 0; x < sdLen; x++ {
		numberOccur := make([]bool, sdLen+1)
		for y := 0; y < sdLen; y++ {
			num := getBoardNum(board[x][y])
			if -1 == num {
				continue
			}
			if numberOccur[num] {
				return false
			}
			numberOccur[num] = true
		}
	}
	// 检查每一行
	for y := 0; y < sdLen; y++ {
		numberOccur := make([]bool, sdLen+1)
		for x := 0; x < sdLen; x++ {
			num := getBoardNum(board[x][y])
			if -1 == num {
				continue
			}
			if numberOccur[num] {
				return false
			}
			numberOccur[num] = true
		}
	}
	// 检查3*3 数独
	for indexX := 0; indexX < sdLen; indexX += 3 {
		for indexY := 0; indexY < sdLen; indexY += 3 {
			numberOccur := make([]bool, sdLen+1)
			for x := indexX; x < indexX+3; x++ {
				for y := indexY; y < indexY+3; y++ {
					num := getBoardNum(board[x][y])
					if -1 == num {
						continue
					}
					if numberOccur[num] {
						return false
					}
					numberOccur[num] = true
				}
			}
		}
	}
	return true
}

// 公共方法: 数组元素转成num
// 空位置返回-1
func getBoardNum(b byte) int {
	if b == '.' {
		return -1
	}
	return int(b - '0')
}
